﻿//https://leetcode.cn/problems/contiguous-array/

class Solution {
public:
    int findMaxLength(vector<int>& nums)
    {
        int m = nums.size();
        unordered_map<int, int> hash;
        hash[0] = -1; //保证数组长度正确
        int ret = 0, sum = 0;
        for (int i = 0; i < m; i++)
        {
            //把0看成-1值
            sum += nums[i] == 0 ? -1 : nums[i];
            //如果sum存在，说明存在一段相同数量01子数组
            //1.因为前面sum更新，如果sum在之前出现过，就说明新加入的值抵消掉了之前出现的0或1
            //2.也就是说，中间必定有一段子数组存在相同个数的0和1
            if (hash.count(sum))
                //此位置减去前面多出来的1或者0(没出现相同数量0和1的子数组长度)
                ret = max(ret, i - hash[sum]);
            else
                //1.走到这里说明没有相同数量的01子数组
                //2.记录此时只有0或者1的位置(没出现相同数量0和1的子数组长度)
                hash[sum] = i;
        }
        return ret;

    }
};